/* PriorityQueue.

   Copyright (C) 2001, 2002, 2003 Stefan Maierhofer.

   Written by Stefan Maierhofer <sm@cg.tuwien.ac.at>

   This file is part of Vecmath.

   Vecmath is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   Vecmath is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with Vecmath; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */

using System;
using System.Collections;

namespace Vecmath.Utils
{


    public class PriorityQueue
    {

        public void Insert(IComparable item)
        {
            data.Add(item);
            size = data.Count;

            int i = size - 1;
            int j = size / 2 - 1;

            while (i > 0 && ((IComparable)data[i]).CompareTo((IComparable)data[j]) < 0)
            {
                object tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;

                i = j;
                j = (i - 1) / 2;
            }
        }

        public IComparable Min
        {
            get { return (size > 0) ? (IComparable)data[0] : null; }
        }

        public IComparable RemoveMin()
        {
            if (size == 0) return null;

            IComparable result = (IComparable)data[0];
            data[0] = data[size-1];
            data.RemoveAt(size-1);
            size--;

            int i = 0;
            int j = 1;
            while (j < size && ((IComparable)data[i]).CompareTo((IComparable)data[j]) > 0)
            {
                object tmp = data[i];
                data[i] = data[j];
                data[j] = tmp;

                i = j;
                j = 2 * i + 1;
            }

            return result;
        }

        public int Size
        {
            get { return size; }
        }

        protected int size = 0;
        protected ArrayList data = new ArrayList();

    }

   

}
